/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-04-11
 * Time: 17:53
 */
//前序中序还原二叉树and中序后序还原二叉树
public class Test {

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int postIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findRootIndex(inorder, inBegin, inEnd, postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder, postorder, rootIndex + 1, inEnd);
        root.left = buildTreeChild(inorder, postorder, inBegin, rootIndex - 1);
        return root;
    }

    private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, preorder.length - 1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
        if (inBegin > inEnd) return null;
        TreeNode root = new TreeNode(preorder[postIndex]);
        int rootIndex = findRootIndex(inorder, inBegin, inEnd, preorder[postIndex]);
        postIndex++;
        root.left = buildTreeChild(preorder, inorder, inBegin, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inEnd);
        return root;
    }
}
